package quick;

import java.util.Random;
public class qiuck {

	public static void main(String[] args) {
		int num=1000000;
		 int[] arr = new int[num];
		Random rand = new Random();
		for(int i=0;i<num;i++){
			arr[i]=rand.nextInt(num);
		}
		PrintArr(arr,num);
		long start = System.nanoTime();
		QuickSort(arr,0,num-1);
		long end = System.nanoTime();
		long traceTime = end-start;
		PrintArr(arr,num);
		System.out.print("\n");
		System.out.println(traceTime);
		
				
}
public static void QuickSort(int arr[] ,int p,int r) {
	int i,j;
	int x;
	i=p;
    j=r;
	x=arr[(i+j)/2];
	do{
		while(arr[i]<x){ i++;}
		while(arr[j]>x){ j--;}
		if(i<=j)
		{
			int tmp=arr[j];
			arr[j]=arr[i];
			arr[i]=tmp;
			i++;
			j--;
			}
		}
	
	while(i<=j);
	if(j>p)
		QuickSort(arr,p,j);
	if(i<r)
		QuickSort(arr,i,r);
}

public static void PrintArr(int arr[],int num){
	System.out.print("\n");
	for(int i=0;i<num;i++){
		System.out.print(arr[i]+",");
		}
	}
}